The technical field of this invention is forward error correction using turbo decoders.
Turbo codes are a type of forward error correction code with powerful capabilities. These codes are becoming widely used in many applications such as wireless handsets, wireless base stations, hard disk drives, wireless local area networks (LANs), satellites and digital television.
Turbo encoding is accomplished by means of concatenation of convolutional codes. FIG. 1A illustrates an example of a prior art rate ⅓ parallel-concatenated turbo encoder. The notation rate ⅓ refers to the configuration of FIG. 1A in which a single input bit stream xk is converted by the encoder into a 3-component bit stream. Input data stream 100 passes unmodified to multiplexer input 106. Two recursive systematic convolutional (RSC) encoders 102 and 103 function in parallel to transform their input bit streams. The resulting bit streams after transformation by RSC encoder 102 forms multiplexer input 107 and after transformation by RSC encoder 103 forms multiplexer input 108. Block 101 is an interleaver (I) which randomly re-arranges the information bits to decorrelate the noise for the decoder. RSC encoder 102 generates a p1k bit stream and RSC encoder 103 generates a p2k bit stream. Under control of a turbo controller function multiplexer 104 reassembles the separate bit streams xk 106, p1k 107 and p2k 108 into the resulting output bit stream xk/p1k/p2k 111.
FIG. 1B illustrates an example of the RSC encoder function which is a part of the blocks 102 or 103. Input data stream 120 passes unmodified to become output x0 131. After transformation by the RSC encoder the resulting bit streams 131, 132 and 133 in prescribed combinations form multiplexer inputs 107 and 108 of FIG. 1A. The precise combinations are determined by the class of turbo encoder being implemented, xc2xd, ⅓, or xc2xc for example. The action of the circuit of FIG. 1B is depicted by a corresponding trellis diagram which is illustrated in FIG. 4 and will be described in the text below.
This transmitted output bit stream 111 of FIG. 1A can be corrupted by transmission through a noisy environment. The function of the decoder at the receiving end is to reconstruct the original bit stream by tracing through multiple passes or iterations through the turbo trellis function.
FIG. 2 illustrates the functional block diagram of a prior art turbo decoder. A single pass through the loop of FIG. 2 is one iteration through the turbo decoder. This iterative decoder generates soft decisions from two maximum-a-posteriori (MAP) blocks 202 and 203. In each iteration MAP block 202 generates extrinsic information W0,k 206 and MAP block 203 generates extrinsic information W1,k 207. First MAP block 202 receives the non-interleaved data xk 200 and data p1k 201 as inputs. Second MAP decoder 203 receives data p2k 211 and interleaved xk data 210 from the interleaver block 208.
FIG. 3 illustrates the functional block diagram of a prior art MAP block. The MAP block of FIG. 3 includes circuit functions similar to those illustrated in FIG. 2. The MAP block calculates three vectors: beta state metrics, alpha state metrics and extrinsics. Both alpha block 302 and beta block 303 calculate state metrics. It is useful to define the function gamma as:
xcex93k=f(Xk,Pk,Wk)xe2x80x83xe2x80x83[1]
where: Xk is the systematic data; Pk is the parity data; and Wk is the extrinsics data.
Input 300 to the alpha state metrics block 302 and input 301 to beta state metrics block 302 are referred to as a-priori inputs. The beta state metrics are generated by beta state metrics block 303. These beta metrics are generated in reverse order and stored in the beta state random access memory (RAM) 304. Next, alpha state metrics are generated by alpha state metrics block 302. The alpha state metrics are not stored because the extrinsic block 305 uses this data as soon as it is generated. The beta state metrics are read from beta RAM 304 in a forward order at the same time as the alpha state metrics are generated. Extrinsic block 305 uses both the alpha and beta state metrics in a forward order to generate the extrinsics Wn,j 306.
The variables for the MAP algorithm are usually represented by the natural logarithm of probabilities. This allows for simplification of very large scale integration (VLSI) implementation. The recursive equations for the alpha and beta state metrics are as follows:                               A                      k            ,            s                          =                  ln          ⁡                      [                                          ∑                s                            ⁢                              exp                ⁢                                  {                                                            A                                              k                        -                        1                                                              +                                          Γ                      k                                                        }                                                      ]                                              [        2        ]                                          B                      k            ,            s                          =                  ln          ⁡                      [                                          ∑                s                            ⁢                              exp                ⁢                                  {                                                            B                                              k                        -                        1                                                              +                                          Γ                      k                                                        }                                                      ]                                              [        3        ]            
where: s is the set of states in the trellis; and xcex93k is as stated in equation [1] above.
FIG. 4 shows the trellis diagram for an 8-state state encoder. For a given state on the trellis, for example state 7 indicated by reference numbers 401 and 402, it is possible to write the probability equation for a given state in the form:
P(7)=[P(3)xc3x97xcex3(001)]+[P(7)xc3x97xcex3(110)]xe2x80x83xe2x80x83[4]
for Alpha and
P(7)=[P(6)xc3x97xcex3(001)]+[P(7)xc3x97xcex3(110)]xe2x80x83xe2x80x83[5]
for Beta.
These equations are said to be of the form:
P=MAX*(A, B)xe2x80x83xe2x80x83[6]
where: A and B are the alpha and beta state metrics given by equations [2] and [3]. Equation 6 is referred to as the xe2x80x98max starxe2x80x99 equation, a simplification of the probability equations. The function P can be further expressed as:
P=MAX*(A, B)=MAX(A, B)+f(xe2x88x92|Axe2x88x92B|)xe2x80x83xe2x80x83[7]
and f(xe2x88x92|Axe2x88x92B|) ranges from 0 to ln(2).
Turbo decoder processing is an iterative process requiring multiple cycles until a low bit-error ratio (BER) solution is obtained. Because the state of the trellis at the start of processing is unknown the probability of the occurrence of all the states in the trellis is initialized to a uniform constant. For each pass through the trellis, the probability of occurrence of a given state will increase or decrease as convergence to the original transmitted data proceeds. After processing through the trellis a number of times a set of states corresponding to the original transmitted data becomes dominant and the state metrics become reliable.
FIG. 4 illustrate a trellis diagram for an 8-state state encoder depicting the possible state transitions from each possible state Sk,x=ABC. For example, for state Sk,4, ABC=001. These states are represented in FIG. 1B by the state of the three registers A 121, B 122 and C 123, respectively. In the decoder, the generation of the alpha state metrics requires processing the data in a forward direction through this trellis and the generation of the beta state metrics requires processing the data in a reverse direction through this trellis. Initial states in the trellis for forward traversal are labeled Sk,x and next states are labeled Sk+1,x. Conversely, initial states in the trellis for reverse direction traversal are labeled Sk+1,x and next states are labeled Sk,x. The nomenclature X/DEF of 403 and 404 of FIG. 4 refers to the next bit xe2x80x98Yxe2x80x99 inserted at the input Xk, 120 of FIG. 1B, followed by the forward slash, followed by the next three bits D, E and F generated respectively at the nodes 131, 132, 133 of FIG. 1B.
FIG. 5 illustrates an example of a prior art VLSI implementation of a four-stage beta state metric architecture. The first stage is an adder tree 501 which sums X, P, W and the beta state metrics depending on the trellis of the encoder. The implementation of the alpha block is the same as the beta block of FIG. 5, except the combinations of the operands in the adder tree. The second stage 502 to 509 is made up of a total of S blocks known as xe2x80x98max star blocksxe2x80x99.
For a given state on the trellis, for example state 7 as already noted in FIG. 4, it is possible to write the probability equation in the form:
P(7)=[P(3)xc3x97xcex3(001)]+[P(7)xc3x97xcex3(110)]xe2x80x83xe2x80x83[8]
for Alpha and
P(7)=[P(6)xc3x97xcex3(001)]+[P(7)xc3x97xcex3(110)]xe2x80x83xe2x80x83[9]
for Beta.
These equations are said to be of the form:
P=MAX*(A, B)xe2x80x83xe2x80x83[10]
The max star equation is a simplification of the probability equations.
The third stage 511 of both the alpha and the beta metrics blocks determines which S-state metrics is the largest or equivalently, which S-state has the highest probability of occurring. The fourth stage 512 subtracts the largest metric from each of the S-state calculated values. The third and fourth stages are normalization stages.
There are corresponding set S-state metrics for each given time k. The state metric with the highest value is the most probable state in the trellis at time k. The effect of normalization is to bound the fixed-point precision and prevent fixed-point overflow. The normalization described here assigns this most probable state with the state value 0 and the state values of other states a negative value.
FIG. 6 illustrates a block diagram of the prior art extrinsic architecture. The first stage 601 is another adder tree which sums the beta state metrics, alpha state metrics and the parity. The other extrinsic stages include two-part max star tree. The first part, max star blocks 602 to 605, calculates the log probability of a xe2x80x981xe2x80x99 in the top half of the tree represented by blocks 602 and 603 and calculates the log probability of a xe2x80x980xe2x80x99 in the bottom half of the tree represented by blocks 604 and 605. The second part of the max star blocks includes blocks 606 and 607. The last stage including max star blocks 608 and 609, and summer 610 subtracts the two log probabilities to generate the extrinsic Wk.
The adder tree 601 generates 2S number of operands for the max star tree. If the bit precision of the state metrics and parity have the same number of bits such as x, then the sum of the three will require x+2 bits for each operand. Note that the result of each addition operation requires one extra bit of precision.
Conventional turbo decoders have implementations that require two""s complement representation and normalization for quantities used in the computation of extrinsic values. This leads to performance loss, specifically added latency, in functional blocks carrying out the required normalization and calculation of these extrinsic values. This invention presents a unique implementation of normalization in the extrinsic block of the turbo decoder that solves the difficulties that accompany normalization, and the generation and use of precision extension in the alpha and beta metric blocks. The implementation achieves improved performance as compared to earlier approaches and does so without the added gate usage and latency resulting from normalization in the alpha metrics and beta metrics blocks. The normalization used obviates the need for normalization in the alpha metrics and beta metrics blocks.